REVIEW (draw a picture of the Collection inheritance hierarchy)

	Collection, List, 
	Set, SortedSet, 
	ArrayList, LinkedList, 
	TreeSet, HashSet


What's a Map?

	Set of key/value pairs
	keys must be unique
	values not unique


What are some examples of Maps?

	phone book (name -> number)
	dictionary (word -> definition)


What are the operations on a Map?

	put
	get
	remove


Map interface

public interface Map {
	int size();
	void clear();
	boolean isEmpty();
	Object put(Object key, Object value);
	Object get(Object key);
	Object remove(Object key);
	boolean containsKey(Object key);
	Set keySet();
	Collection values();
	Set entrySet();
	public interface Entry {
		Object getKey();
		Object getValue();
	}
}


Why does Map not extend Collection?

	a map is a collection of pairs
	don't want to work directly with the pairs
	want to work with keys and values independently


Why does Map not provide an iterator factory method?

	don't wan't to iterate over the pairs
	want to iterate over keys


DEMO	(Demo6.java, iterating over a Map)


DEMO	(Demo8.java, word frequency counter)



What's a SortedMap?

	Map with entries sorted by key
	keySet and entrySet return SortedSets


DEMO	(change Map to SortedMap)


Does SortedMap have any methods in addition to those in Map?


SortedMap Interface

public interface SortedMap extends Map {
       Object firstKey();
       Object lastKey();
}


Add Map stuff to Collection hierarchy drawing

	Map
	SortedMap
	HashMap
	TreeMap



What's a Cross-Reference Generator?

	read source file
	find identifiers
	output identifiers in sorted order
	for each identifier x list line numbers where x occurs


What data types could be used in a Cross-Reference Generator?

	Map to store (identifier/list of line numbers) pairs
	List to store list of line numbers


What's the algorithm used in a Cross-Reference Generator?

	loop reading identifiers
		if identifier not in Map
			make new List
			add (identifier/List) to Map
		add line number to List
	iterate over Map
		output identifier
		iterate over List
			output line number


DEMO	(show and run Xref.java)